#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int tallestBillboard(vector<int>& rods) {
        unordered_map<int, int> dp;
        dp[0] = 0;
        for (auto i : rods) {
            unordered_map<int, int> tmp = dp;
            for (auto it : tmp) {
                int key = it.first;
                dp[key + i] = max(dp[key + i], tmp[key] + i);
                dp[key - i] = max(dp[key - i], tmp[key]);
            }
        }
        return dp[0];
    }
};